import java.util.List;

/**
 * Created by L.jp
 * Description:给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。
 *
 * 数据范围： 0\leq n\leq10000≤n≤1000
 * 要求：空间复杂度 O(1)O(1) ，时间复杂度 O(n)O(n) 。
 *
 * 如当输入链表{1,2,3}时，
 * 经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。
 * User: 86189
 * Date: 2022-05-05
 * Time: 20:07
 */
class ListNode {
    int val;
    ListNode next = null;
    
    ListNode(int val) {
        this.val = val;
    }
    
    @Override
    public String toString() {
        return "ListNode{" +
                "val=" + val +
                ", next=" + next +
                '}';
    }
}
public class solution {
    public static ListNode ReverseList(ListNode head) {
        //第一种方法：迭代法
        //首先判断空链表的情况
//        if(head==null){
//            return head;
//        }
//        //遍历链表的节点
//        ListNode cur=head;
//        //新的头节点
//        ListNode newH=null;
//        /*方法：给定一个新的头结点newH，先把cur的后继节点保存，让newH作为cur的前驱节点
//        *      然后让newH指向cur,cur指向后继节点，就这样一直反复，直到cur==null */
//        while (cur != null) {
//            //保存后继节点
//            ListNode curNext=cur.next;
//            cur.next=newH;
//            newH=cur;
//            cur=curNext;
//        }
//        return newH;
        
        //方法二：递归
        if(head==null || head.next == null){
            return head;
        }
        //每一步都是找下一个节点，直到此节点为空或者此节点的下一个节点为空
        ListNode newh=ReverseList(head.next);
        //我们以1->2->3->4为例，当我们遍历到3时，我们传参是4，此时4！=null但是4.next==null
        // 所以此时终于有返回值了newh就是4，因为是遍历到3的时候把4传过去了，所以第一个返回之后的head就是3
        //那么反转3->4就是3.next.next=3;然后把原来的3->4取消指向，就完成了反转
        //newh的值一直是5，不会改变，return时改变的是head的值，依次是3,2,1
        head.next.next=head;
        head.next=null;
        return newh;
    }
    
    public static void main(String[] args) {
        ListNode head=new ListNode(1);
        int num=head.val;
        //给出5个节点
        int n=5;
        ListNode cur=head;
        while(n>0) {
            cur.next=new ListNode(num++);
            cur=cur.next;
            n--;
        }
        System.out.println(ReverseList(head));
    }
}
